package com.mlamp.二叉树;

import sun.reflect.generics.tree.Tree;

import java.util.LinkedList;

public class 公共父节点 {

    public static void main(String[] args) {
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(5);
        root.right = new TreeNode(1);
        root.left.left = new TreeNode(6);
        root.left.right = new TreeNode(2);
        root.right.left = new TreeNode(0);
        root.right.right = new TreeNode(8);
        root.left.right.left = new TreeNode(7);
        root.left.right.left = new TreeNode(4);

        公共父节点 instance = new 公共父节点();
        TreeNode treeNode = instance.lstCommonAncestorB(root, root.right.left, root.right.right);
        System.out.println(treeNode.val);

        treeNode = instance.lstCommonAncestorC(root, root.right.right, root.right.left);
        System.out.println(treeNode.val);

        coreD(root, root.right.right, root.right.left.left);

    }

    public Integer lowestCommonAncestor3(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || p == null || q == null) return null;

        LinkedList<Integer> pathp = new LinkedList<>();
        LinkedList<Integer> pathq = new LinkedList<>();
        pathp.add(root.val);
        pathq.add(root.val);

           path(root, p, pathp);
        path(root, q, pathq);

        Integer lca = null;
        for (int i = 0; i < pathp.size() && i < pathq.size(); i++) {
            if (pathp.get(i) == pathq.get(i)) lca = pathp.get(i);
            else break;
        }
        return lca;
    }


    public Integer lowestCommonAncestor33(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || p == null || q == null) return null;
        LinkedList<TreeNode> ptrace = new LinkedList<>();
        LinkedList<TreeNode> qtrace = new LinkedList<>();
        ptrace.add(root);
        qtrace.add(root);
        path3(root, p, ptrace);
        path3(root, q, qtrace);
        Integer lca = null;
        for (int i = 0; i < ptrace.size() && i < qtrace.size(); i++) {
            if (ptrace.get(i) == qtrace.get(i)) lca = ptrace.get(i).val;
            else break;
        }
        return lca;
    }


    public Integer lowestCommonAncestor4(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || p == null || q == null) return null;
        LinkedList<Integer> pathP = new LinkedList<>();
        LinkedList<Integer> pathQ = new LinkedList<>();
        pathP.add(root.val);
        pathP.add(root.val);
        path2(root, p, pathP);
        path2(root, q, pathQ);
        Integer lca = null;
        for (int i = 0; i < pathP.size() && i < pathQ.size(); i++) {
            if (pathP.get(i) == pathQ.get(i)) lca = pathP.get(i);
            else break;
        }
        return lca;
    }


    public static void coreA(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || p == null || q == null) return;
        LinkedList<Integer> traceP = new LinkedList<>();
        LinkedList<Integer> traceQ = new LinkedList<>();
        traceP.add(root.val);
        traceQ.add(root.val);
        pathA(root, p, traceP);
        pathA(root, q, traceQ);
        Integer res = null;
        for (int i = 0; i < traceP.size() && i < traceQ.size(); i++) {
            if (traceP.get(i) == traceQ.get(i)) res = traceP.get(0);
            else break;
        }
    }

    public static void coreB(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || p == null || q == null) return;
        LinkedList<Integer> traceP = new LinkedList<>();
        LinkedList<Integer> traceQ = new LinkedList<>();
        traceP.add(root.val);
        traceQ.add(root.val);
        pathB(root, p, traceP);
        pathB(root, q, traceQ);
        Integer res = null;
        for (int i = 0; i < traceP.size() && i < traceQ.size(); i++) {
            if (traceP.get(i) == traceQ.get(i)) res = traceP.get(i);
            else break;
        }
        System.out.println("res: " + res);
    }


    public static void coreD(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || p == null || q == null) return;
        LinkedList<Integer> pTrace = new LinkedList<>();
        LinkedList<Integer> qTrace = new LinkedList<>();
        pTrace.add(root.val);
        qTrace.add(root.val);
        pathD(root, p, pTrace);
        pathD(root, q, qTrace);
        Integer res = null;
        for (int i = 0; i < pTrace.size() && i < qTrace.size(); i++) {
            if (pTrace.get(i) == qTrace.get(i)) res = pTrace.get(i);
            else break;
        }
        System.out.println("res " + res);
    }


    public static boolean pathA(TreeNode root, TreeNode p, LinkedList<Integer> trace) {
        if (root == p) return true;
        if (root.left != null) {
            trace.add(root.left.val);
            if (pathA(root.left, p, trace)) return true;
            trace.removeLast();
        }
        if (root.right != null) {
            trace.add(root.right.val);
            if (pathA(root.right, p, trace)) return true;
            trace.removeLast();
        }
        return false;
    }


    public static boolean pathD(TreeNode root, TreeNode p, LinkedList<Integer> trace) {
        if (root == p) return true;
        if (root.left != null) {
            trace.add(root.left.val);
            if (pathD(root.left, p, trace)) return true;
            trace.removeLast();
        }
        if (root.right != null) {
            trace.add(root.right.val);
            if (pathD(root.right, p, trace)) return true;
            trace.removeLast();
        }
        return false;

    }


    /**
     * 求给定节点到跟节点的路径
     *
     * @param root
     * @param p
     * @param trace
     * @return
     */

    public static boolean pathC(TreeNode root, TreeNode p, LinkedList<Integer> trace) {
        if (root == p) return true;
        if (root.left != null) {
            trace.add(root.left.val);
            if (pathC(root.left, p, trace)) return true;
            trace.removeLast();
        }
        if (root.right != null) {
            trace.add(root.right.val);
            if (pathC(root.right, p, trace)) return true;
            trace.removeLast();
        }
        return false;
    }

    public static boolean pathB(TreeNode root, TreeNode p, LinkedList<Integer> trace) {
        if (root == p) return true;
        if (root.left != null) {
            trace.add(root.left.val);
            if (pathB(root.left, p, trace)) return true;
            trace.removeLast();
        }
        if (root.right != null) {
            trace.add(root.right.val);
            if (pathB(root.right, p, trace)) return true;
            trace.removeLast();
        }
        return false;
    }


    public static boolean path2(TreeNode root, TreeNode p, LinkedList<Integer> trace) {
        if (root == p) return true;
        if (root.left != null) {
            trace.add(root.left.val);
            if (path(root.left, p, trace)) return true;
            trace.removeLast();
        }

        if (root.right != null) {
            trace.add(root.right.val);
            if (path(root.right, p, trace)) return true;
            trace.removeLast();
        }
        return false;
    }


    public static boolean path(TreeNode root, TreeNode p, LinkedList<Integer> trace) {
        if (root == p) {
            return true;
        }

        if (root.left != null) {
            trace.add(root.left.val);
            if (path(root.left, p, trace)) return true;
            trace.removeLast();
        }

        if (root.right != null) {
            trace.add(root.right.val);
            if (path(root.right, p, trace)) return true;
            trace.removeLast();
        }
        return false;
    }


    public static boolean path3(TreeNode root, TreeNode p, LinkedList<TreeNode> trace) {
        if (root == p) return true;
        if (root.left != null) {
            trace.add(root.left);
            if (path3(root.left, p, trace)) return false;
            trace.removeLast();
        }
        if (root.right != null) {
            trace.add(root.right);
            if (path3(root.right, p, trace)) return false;
            trace.removeLast();
        }
        return false;
    }

    /**
     * 递归求解二叉树的最近公共父节点
     *
     * @param root
     * @param p
     * @param q
     * @return
     */

    public TreeNode lstCommonAncestorB(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || root == p || root == q) return root;
        TreeNode left = lstCommonAncestorB(root.left, p, q);
        TreeNode right = lstCommonAncestorB(root.right, p, q);
        return left != null && right != null ? root : left == null ? right : left;
    }

    public TreeNode lstCommonAncestorC(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || root == p || root == q) return root;
        TreeNode left = lstCommonAncestorC(root.left, p, q);
        TreeNode right = lstCommonAncestorC(root.right, p, q);
        return left != null && right != null ? root : left != null ? left : right;
    }


    public TreeNode lowestCommonAncestor43(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || root == p || root == q) {
            return root;
        }
        TreeNode left = lowestCommonAncestor43(root.left, p, q);
        TreeNode right = lowestCommonAncestor43(root.right, p, q);
        return (left != null && right != null) ? root : left == null ? right : left;
    }


    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || root == p || root == q) {
            return root;
        }
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        return left != null && right != null ? root : left == null ? right : left;
    }

    public TreeNode lowestCommonAncestor2(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || root == p || root == q) return root;
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        return left != null && right != null ? root : left == null ? right : left;
    }


    //递归算法
    public TreeNode lowestCommonAncestorA(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || root == q || root == p) return root;
        TreeNode left = lowestCommonAncestorA(root.left, p, q);
        TreeNode right = lowestCommonAncestorA(root.right, p, q);
        return left != null && right != null ? root : left == null ? right : left;
    }

    //递归算法
    public TreeNode lowestCommonAncestorB(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || root == p || root == q) return root;
        TreeNode left = lowestCommonAncestorB(root.left, p, q);
        TreeNode right = lowestCommonAncestorB(root.right, p, q);
        return left != null && right != null ? root : left == null ? right : left;
    }


    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

}
